package DoExercise.HSP_ZCY.A008_树.A001_普通二叉树;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: Du
 * @Date: 2021/7/13 16:05
 *
 * 二叉树的增删改查操作
 *
 *
 */
public class C13_二叉树的增删改查
{
    
    /**
     * 删除整棵树，因为需要先删除子节点，再删除根节点
     * 所以可以采用后续遍历，左右根。
     * <p>
     * 该方法暂时不知道如何返回删除后的树
     * 因为返回的一定是空
     * 方法的意义就是了解后序遍历的用法
     *
     * @param root
     */
    public void deleteTree(TreeNode root)
    {
        if (root == null)
        {
            return;
        }
        deleteTree(root.left);
        deleteTree(root.right);
        root = null;
    }
    
    
    /**
     * 删除树节点
     * 思路：
     * (1) 删除节点没有子节点时
     * (2) 删除节点有一个子节点时
     * (3) 删除节点有左右子节点时
     */
    public TreeNode deleteTreeNode(TreeNode root, TreeNode delNode)
    {
        if (root == null) return null;
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode tempNode = null, childLeft = null, childRight = null, deepestNode;
        boolean left = false, right = false;
        queue.offer(root);
        
        while (!queue.isEmpty())
        {
            tempNode = queue.poll();
            
            if (tempNode.left != null)
            {
                //找到删除的节点
                if (tempNode.left.value == delNode.value)
                {
                    //判断被删除节点的左子节点和右子节点是否为null
                    if (tempNode.left.left != null)
                    {
                        childLeft = tempNode.left.left;
                        left = true;
                    }
                    if (tempNode.left.right != null)
                    {
                        childRight = tempNode.left.right;
                        right = true;
                    }
                    //被删除节点存在子节点
                    if (left || right)
                    {
                        deepestNode = getDeepestTreeNode(root);
                        if (left && right)
                        {
                            tempNode.left = deepestNode;
                            deepestNode.left = childLeft;
                            deepestNode.right = childRight;
                        } else if (left)
                        {
                            tempNode.left = deepestNode;
                            deepestNode.left = childLeft;
                        } else if (right)
                        {
                            tempNode.left = deepestNode;
                            deepestNode.right = childRight;
                        }
                    } else
                    {
                        tempNode = null;
                    }
                    return tempNode;
                } else
                {
                    queue.add(tempNode.left);
                }
            }
            if (tempNode.right != null)
            {
                //找到删除的节点
                if (tempNode.right.value == delNode.value)
                {
                    //判断被删除节点的左子节点和右子节点是否为null
                    if (tempNode.right.left != null)
                    {
                        childLeft = tempNode.right.left;
                        left = true;
                    }
                    if (tempNode.right.right != null)
                    {
                        childRight = tempNode.right.right;
                        right = true;
                    }
                    //被删除节点存在子节点
                    if (left || right)
                    {
                        deepestNode = getDeepestTreeNode(root);
                        if (left && right)
                        {
                            tempNode.right = deepestNode;
                            deepestNode.left = childLeft;
                            deepestNode.right = childRight;
                        } else if (left)
                        {
                            tempNode.right = deepestNode;
                            deepestNode.left = childLeft;
                        } else if (right)
                        {
                            tempNode.right = deepestNode;
                            deepestNode.right = childRight;
                        }
                    } else
                    {
                        tempNode = null;
                    }
                    return tempNode;
                } else
                {
                    queue.add(tempNode.right);
                }
            }
        }
        return tempNode;
    }
    
    
    /**
     * 求二叉树的高度
     * <p>
     * 递归法求高度，左右两侧分开递归，递归至最下层节点，在逐层合并。
     */
    public int HighOfTree(TreeNode root)
    {
        int leftHeight, rightHeight;
        if (root == null)
        {
            return 0;
        } else
        {
            leftHeight = HighOfTree(root.left);
            rightHeight = HighOfTree(root.right);
            
            if (leftHeight > rightHeight)
            {
                return leftHeight + 1;
            } else
            {
                return rightHeight + 1;
            }
        }
    }
    
    
    /**
     * 获取二叉树最深的节点
     * <p>
     * 层序遍历，获取最后一个节点，
     * 获取后需要将最后一个节点和之前节点的联系切断（重点）
     *
     * @return
     */
    public TreeNode getDeepestTreeNode(TreeNode root)
    {
        if (root == null) return null;
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode tempNode = null, preLeft = null, preRight = null;
        queue.offer(root);
        
        while (!queue.isEmpty())
        {
            tempNode = queue.poll();
            
            if (tempNode.left != null)
            {
                preLeft = tempNode;
                queue.add(tempNode.left);
            } else
            {
                if (!queue.isEmpty())
                {
                    preLeft = null;
                }
            }
            
            if (tempNode.right != null)
            {
                preRight = tempNode;
                queue.add(tempNode.right);
            } else
            {
                if (!queue.isEmpty())
                {
                    preRight = null;
                }
            }
        }
        
        //切断最深节点和其上级节点之间的联系
        if (preLeft != null)
        {//Tree引用的逻辑是怎样的？为什么改变任意一个赋值变量的值最后都会改变root的值？
            preLeft.left = null;
        } else if (preRight != null)
        {
            preLeft.right = null;
        } else if (preLeft != null && preRight != null)
        {
            preLeft.right = null;
        }
        
        return tempNode;
    }
    
    public static class TreeNode
    {
        public int value;
        public TreeNode left;
        public TreeNode right;
        
        public TreeNode(int data)
        {
            this.value = data;
        }
    }
}
